/**
 * wasavi: vi clone implemented in javascript
 * =============================================================================
 *
 *
 * @author akahuku@gmail.com
 */
/**
 * Copyright 2012-2017 akahuku, akahuku@gmail.com
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

(function (g) {

'use strict';

// Zs letters in UnicodeData.txt of Unicode 9.0.0
// generated by "src/uncode-tools/make-prop-regex.js --general-category=Zs"
const REGEX_ZS = new RegExp('[\
\\u0009\\u0020\\u00A0\\u1680\\u2000\\u2001\\u2002\\u2003\\u2004\\u2005\\u2006\
\\u2007\\u2008\\u2009\\u200A\\u202F\\u205F\\u3000\
]');

// Pe letters in UnicodeData.txt of Unicode 9.0.0
// generated by "src/unicode-tools/make-prop-regex.js --general-category=Pe"
const REGEX_PE = new RegExp('[\
\\u0029\\u005D\\u007D\\u0F3B\\u0F3D\\u169C\\u2046\\u207E\\u208E\\u2309\\u230B\
\\u232A\\u2769\\u276B\\u276D\\u276F\\u2771\\u2773\\u2775\\u27C6\\u27E7\\u27E9\
\\u27EB\\u27ED\\u27EF\\u2984\\u2986\\u2988\\u298A\\u298C\\u298E\\u2990\\u2992\
\\u2994\\u2996\\u2998\\u29D9\\u29DB\\u29FD\\u2E23\\u2E25\\u2E27\\u2E29\\u3009\
\\u300B\\u300D\\u300F\\u3011\\u3015\\u3017\\u3019\\u301B\\u301E\\u301F\\uFD3E\
\\uFE18\\uFE36\\uFE38\\uFE3A\\uFE3C\\uFE3E\\uFE40\\uFE42\\uFE44\\uFE48\\uFE5A\
\\uFE5C\\uFE5E\\uFF09\\uFF3D\\uFF5D\\uFF60\\uFF63\
]');

// Sentence_Terminal letters in PropList.txt of Unicode 9.0.0
// generated by "src/unicode-tools/make-prop-regex.js --prop-list=Sentence_Terminal"
const REGEX_SENTENCE_TERMINAL = new RegExp('[\
\\u0700-\\u0702	\\u0964\\u104A\\u1367\\u1735\\u1944\\u1AA8-\\u1AAB	\
\\u1B5A\\u1B5E\\u1C3B\\u1C7E\\u203C\\u2047-\\u2049	\\uA60E\\uA876\\uA8CE\
\\uA9C8\\uAA5D-\\uAA5F	\\uAAF0\\uFE56\
]');

// Sentence_Terminal letters in PropList.txt of Unicode 9.0.0
// generated by "src/unicode-tools/make-prop-regex.js --prop-list=Sentence_Terminal"
const REGEX_STERM = new RegExp('[\
\\u0021\\u002E\\u003F\\u0589\\u061F\\u06D4\\u0700-\\u0702\\u07F9\\u0964\\u0965\
\\u104A\\u104B\\u1362\\u1367\\u1368\\u166E\\u1735\\u1736\\u1803\\u1809\\u1944\
\\u1945\\u1AA8-\\u1AAB\\u1B5A\\u1B5B\\u1B5E\\u1B5F\\u1C3B\\u1C3C\\u1C7E\\u1C7F\
\\u203C\\u203D\\u2047-\\u2049\\u2E2E\\u2E3C\\u3002\\uA4FF\\uA60E\\uA60F\\uA6F3\
\\uA6F7\\uA876\\uA877\\uA8CE\\uA8CF\\uA92F\\uA9C8\\uA9C9\\uAA5D-\\uAA5F\\uAAF0\
\\uAAF1\\uABEB\\uFE52\\uFE56\\uFE57\\uFF01\\uFF0E\\uFF1F\\uFF61\
]');

// Terminal_Punctuation letters in PropList.txt of Unicode 9.0.0
// generated by "src/unicode-tools/make-prop-regex.js --prop-list=Terminal_Punctuation"
const REGEX_PTERM = new RegExp('[\
\\u0021\\u002C\\u002E\\u003A\\u003B\\u003F\\u037E\\u0387\\u0589\\u05C3\\u060C\
\\u061B\\u061F\\u06D4\\u0700-\\u070A\\u070C\\u07F8\\u07F9\\u0830-\\u083E\
\\u085E\\u0964\\u0965\\u0E5A\\u0E5B\\u0F08\\u0F0D-\\u0F12\\u104A\\u104B\
\\u1361-\\u1368\\u166D\\u166E\\u16EB-\\u16ED\\u1735\\u1736\\u17D4-\\u17D6\
\\u17DA\\u1802-\\u1805\\u1808\\u1809\\u1944\\u1945\\u1AA8-\\u1AAB\\u1B5A\
\\u1B5B\\u1B5D-\\u1B5F\\u1C3B-\\u1C3F\\u1C7E\\u1C7F\\u203C\\u203D\
\\u2047-\\u2049\\u2E2E\\u2E3C\\u2E41\\u3001\\u3002\\uA4FE\\uA4FF\
\\uA60D-\\uA60F\\uA6F3-\\uA6F7\\uA876\\uA877\\uA8CE\\uA8CF\\uA92F\
\\uA9C7-\\uA9C9\\uAA5D-\\uAA5F\\uAADF\\uAAF0\\uAAF1\\uABEB\\uFE50-\\uFE52\
\\uFE54-\\uFE57\\uFF01\\uFF0C\\uFF0E\\uFF1A\\uFF1B\\uFF1F\\uFF61\\uFF64\
]');

// Ideographic letters in Scripts.txt of Unicode 9.0.0
// generated by "src/uncode-tools/make-scripts.js --han"
const REGEX_HAN_FAMILY = new RegExp('[' + [
	/* Chinese */
	'\\u2E80-\\u2EFF',		// CJK Radicals Supplement
	'\\u2F00-\\u2FDF',		// Kangxi Radicals
	'\\u3100-\\u312F',		// Bopomofo
	'\\u31A0-\\u31BF',		// Bopomofo Extended
	'\\u3400-\\u4DBF',		// CJK Unified Ideographs Extension A
	'\\u4E00-\\u9FCF',		// CJK Unified Ideographs (Han)
	'\\uF900-\\uFAFF',		// CJK Compatibility Ideographs

	/* Japanese */
	'\\u3040-\\u309F',		// Hiragana
	'\\u30A0-\\u30FF',		// Katakana
	'\\u3190-\\u319F',		// Kanbun
	'\\u31F0-\\u31FF',		// Katakana Phonetic Extensions
	'\\uFF65-\\uFF9F',		// Halfwidth Katakana

	/* Korean */
	'\\u1100-\\u11FF',		// Hangul Jamo
	'\\u3130-\\u318F',		// Hangul Compatibility Jamo
	'\\uA960-\\uA97F',		// Hangul Jamo Extended-A
	'\\uAC00-\\uD7AF',		// Hangul Syllables
	'\\uD7B0-\\uD7FF',		// Hangul Jamo Extended-B
	'\\uFFA0-\\uFFDC',		// Halfwidth Jamo

	/* Yi */
	'\\uA000-\\uA48F',		// Yi Syllables
	'\\uA490-\\uA4CF'		// Yi Radicals
].join('') + ']|' + [
	/* Chinese, CJK Unified Ideographs Extension B (U+20000 - U+2A6DF) */
	'[\\uD840-\\uD868][\\uDC00-\\uDFFF]|\\uD869[\\uDC00-\\uDEDF]',
	/* Chinese, CJK Unified Ideographs Extension C (U+2A700 - U+2B73F) */
	'\\uD869[\\uDF00-\\uDFFF]|[\\uD86A-\\uD86C][\\uDC00-\\uDFFF]|\\uD86D[\\uDC00-\\uDF3F]',
	/* Chinese, CJK Unified Ideographs Extension D (U+2B740 - U+2B81F) */
	'\\uD86D[\\uDF40-\\uDFFF]|\\uD86E[\\uDC00-\\uDC1F]',
	/* Chinese, CJK Unified Ideographs Extension E (U+2B820 - U+2CEAF) */
	'\\uD86E[\\uDC20-\\uDFFF]|[\\uD86F-\\uD872][\\uDC00-\\uDFFF]|\\uD873[\\uDC00-\\uDEAF]',
	/* Chinese, CJK Compatibility Ideographs Supplement (U+2F800 - U+2FA1F) */
	'\\uD87E[\\uDC00-\\uDE1F]',
	/* Japanese, Kana Supplement (U+1B000 - U+1B0FF) */
	'\\uD82C[\\uDC00-\\uDCFF]'
].join('|'));

// not(/[ZLN]./) of General Category in Scripts.txt of Unicode 9.0.0
// generated by "src/unicode-tools/make-scripts.js --nonletters"
const REGEX_NON_LETTER = new RegExp('[\
\\u0000-\\u001F\\u0021-\\u002F\\u003A-\\u0040\\u005B-\\u0060\\u007B-\\u009F\\u00A1-\\u00A9\
\\u00AB-\\u00B1\\u00B4\\u00B6-\\u00B8\\u00BB\\u00BF\\u00D7\\u00F7\\u02C2-\\u02C5\\u02D2-\\u02DF\
\\u02E5-\\u02EB\\u02ED\\u02EF-\\u036F\\u0375\\u037E\\u0384\\u0385\\u0387\\u03F6\\u0482-\\u0489\
\\u055A-\\u055F\\u0589\\u058A\\u058D-\\u058F\\u0591-\\u05C7\\u05F3\\u05F4\\u0600-\\u061C\\u061E\\u061F\
\\u064B-\\u065F\\u066A-\\u066D\\u0670\\u06D4\\u06D6-\\u06E4\\u06E7-\\u06ED\\u06FD\\u06FE\\u0700-\\u070D\
\\u070F\\u0711\\u0730-\\u074A\\u07A6-\\u07B0\\u07EB-\\u07F3\\u07F6-\\u07F9\\u0816-\\u0819\\u081B-\\u0823\
\\u0825-\\u0827\\u0829-\\u082D\\u0830-\\u083E\\u0859-\\u085B\\u085E\\u08D4-\\u0903\\u093A-\\u093C\
\\u093E-\\u094F\\u0951-\\u0957\\u0962-\\u0965\\u0970\\u0981-\\u0983\\u09BC\\u09BE-\\u09C4\\u09C7\\u09C8\
\\u09CB-\\u09CD\\u09D7\\u09E2\\u09E3\\u09F2\\u09F3\\u09FA\\u09FB\\u0A01-\\u0A03\\u0A3C\\u0A3E-\\u0A42\
\\u0A47\\u0A48\\u0A4B-\\u0A4D\\u0A51\\u0A70\\u0A71\\u0A75\\u0A81-\\u0A83\\u0ABC\\u0ABE-\\u0AC5\
\\u0AC7-\\u0AC9\\u0ACB-\\u0ACD\\u0AE2\\u0AE3\\u0AF0\\u0AF1\\u0B01-\\u0B03\\u0B3C\\u0B3E-\\u0B44\
\\u0B47\\u0B48\\u0B4B-\\u0B4D\\u0B56\\u0B57\\u0B62\\u0B63\\u0B70\\u0B82\\u0BBE-\\u0BC2\\u0BC6-\\u0BC8\
\\u0BCA-\\u0BCD\\u0BD7\\u0BF3-\\u0BFA\\u0C00-\\u0C03\\u0C3E-\\u0C44\\u0C46-\\u0C48\\u0C4A-\\u0C4D\
\\u0C55\\u0C56\\u0C62\\u0C63\\u0C7F\\u0C81-\\u0C83\\u0CBC\\u0CBE-\\u0CC4\\u0CC6-\\u0CC8\\u0CCA-\\u0CCD\
\\u0CD5\\u0CD6\\u0CE2\\u0CE3\\u0D01-\\u0D03\\u0D3E-\\u0D44\\u0D46-\\u0D48\\u0D4A-\\u0D4D\\u0D4F\
\\u0D57\\u0D62\\u0D63\\u0D79\\u0D82\\u0D83\\u0DCA\\u0DCF-\\u0DD4\\u0DD6\\u0DD8-\\u0DDF\\u0DF2-\\u0DF4\
\\u0E31\\u0E34-\\u0E3A\\u0E3F\\u0E47-\\u0E4F\\u0E5A\\u0E5B\\u0EB1\\u0EB4-\\u0EB9\\u0EBB\\u0EBC\
\\u0EC8-\\u0ECD\\u0F01-\\u0F1F\\u0F34-\\u0F3F\\u0F71-\\u0F87\\u0F8D-\\u0F97\\u0F99-\\u0FBC\
\\u0FBE-\\u0FCC\\u0FCE-\\u0FDA\\u102B-\\u103E\\u104A-\\u104F\\u1056-\\u1059\\u105E-\\u1060\
\\u1062-\\u1064\\u1067-\\u106D\\u1071-\\u1074\\u1082-\\u108D\\u108F\\u109A-\\u109F\\u10FB\\u135D-\\u1368\
\\u1390-\\u1399\\u1400\\u166D\\u166E\\u169B\\u169C\\u16EB-\\u16ED\\u1712-\\u1714\\u1732-\\u1736\
\\u1752\\u1753\\u1772\\u1773\\u17B4-\\u17D6\\u17D8-\\u17DB\\u17DD\\u1800-\\u180E\\u1885\\u1886\
\\u18A9\\u1920-\\u192B\\u1930-\\u193B\\u1940\\u1944\\u1945\\u19DE-\\u19FF\\u1A17-\\u1A1B\\u1A1E\\u1A1F\
\\u1A55-\\u1A5E\\u1A60-\\u1A7C\\u1A7F\\u1AA0-\\u1AA6\\u1AA8-\\u1AAD\\u1AB0-\\u1ABE\\u1B00-\\u1B04\
\\u1B34-\\u1B44\\u1B5A-\\u1B7C\\u1B80-\\u1B82\\u1BA1-\\u1BAD\\u1BE6-\\u1BF3\\u1BFC-\\u1BFF\
\\u1C24-\\u1C37\\u1C3B-\\u1C3F\\u1C7E\\u1C7F\\u1CC0-\\u1CC7\\u1CD0-\\u1CE8\\u1CED\\u1CF2-\\u1CF4\
\\u1CF8\\u1CF9\\u1DC0-\\u1DF5\\u1DFB-\\u1DFF\\u1FBD\\u1FBF-\\u1FC1\\u1FCD-\\u1FCF\\u1FDD-\\u1FDF\
\\u1FED-\\u1FEF\\u1FFD\\u1FFE\\u200B-\\u2027\\u202A-\\u202E\\u2030-\\u205E\\u2060-\\u2064\\u2066-\\u206F\
\\u207A-\\u207E\\u208A-\\u208E\\u20A0-\\u20BE\\u20D0-\\u20F0\\u2100\\u2101\\u2103-\\u2106\\u2108\\u2109\
\\u2114\\u2116-\\u2118\\u211E-\\u2123\\u2125\\u2127\\u2129\\u212E\\u213A\\u213B\\u2140-\\u2144\
\\u214A-\\u214D\\u214F\\u218A\\u218B\\u2190-\\u23FE\\u2400-\\u2426\\u2440-\\u244A\\u249C-\\u24E9\
\\u2500-\\u2775\\u2794-\\u2B73\\u2B76-\\u2B95\\u2B98-\\u2BB9\\u2BBD-\\u2BC8\\u2BCA-\\u2BD1\
\\u2BEC-\\u2BEF\\u2CE5-\\u2CEA\\u2CEF-\\u2CF1\\u2CF9-\\u2CFC\\u2CFE\\u2CFF\\u2D70\\u2D7F\\u2DE0-\\u2E2E\
\\u2E30-\\u2E44\\u2E80-\\u2E99\\u2E9B-\\u2EF3\\u2F00-\\u2FD5\\u2FF0-\\u2FFB\\u3001-\\u3004\
\\u3008-\\u3020\\u302A-\\u3030\\u3036\\u3037\\u303D-\\u303F\\u3099-\\u309C\\u30A0\\u30FB\\u3190\\u3191\
\\u3196-\\u319F\\u31C0-\\u31E3\\u3200-\\u321E\\u322A-\\u3247\\u3250\\u3260-\\u327F\\u328A-\\u32B0\
\\u32C0-\\u32FE\\u3300-\\u33FF\\u4DC0-\\u4DFF\\uA490-\\uA4C6\\uA4FE\\uA4FF\\uA60D-\\uA60F\\uA66F-\\uA67E\
\\uA69E\\uA69F\\uA6F0-\\uA6F7\\uA700-\\uA716\\uA720\\uA721\\uA789\\uA78A\\uA802\\uA806\\uA80B\
\\uA823-\\uA82B\\uA836-\\uA839\\uA874-\\uA877\\uA880\\uA881\\uA8B4-\\uA8C5\\uA8CE\\uA8CF\\uA8E0-\\uA8F1\
\\uA8F8-\\uA8FA\\uA8FC\\uA926-\\uA92F\\uA947-\\uA953\\uA95F\\uA980-\\uA983\\uA9B3-\\uA9CD\\uA9DE\\uA9DF\
\\uA9E5\\uAA29-\\uAA36\\uAA43\\uAA4C\\uAA4D\\uAA5C-\\uAA5F\\uAA77-\\uAA79\\uAA7B-\\uAA7D\\uAAB0\
\\uAAB2-\\uAAB4\\uAAB7\\uAAB8\\uAABE\\uAABF\\uAAC1\\uAADE\\uAADF\\uAAEB-\\uAAF1\\uAAF5\\uAAF6\
\\uAB5B\\uABE3-\\uABED\\uFB1E\\uFB29\\uFBB2-\\uFBC1\\uFD3E\\uFD3F\\uFDFC\\uFDFD\\uFE00-\\uFE19\
\\uFE20-\\uFE52\\uFE54-\\uFE66\\uFE68-\\uFE6B\\uFEFF\\uFF01-\\uFF0F\\uFF1A-\\uFF20\\uFF3B-\\uFF40\
\\uFF5B-\\uFF65\\uFFE0-\\uFFE6\\uFFE8-\\uFFEE\\uFFF9-\\uFFFD\
]');

// line break property in Unicode undefined
// generated by "src/unicode-tool/make-linebreak-dict.js --js"
const BREAK_PROP = {
	OP:   0,
	CL:   1,
	CP:   2,
	QU:   3,
	GL:   4,
	NS:   5,
	EX:   6,
	SY:   7,
	IS:   8,
	PR:   9,
	PO:  10,
	NU:  11,
	AL:  12,
	HL:  13,
	ID:  14,
	IN:  15,
	HY:  16,
	BA:  17,
	BB:  18,
	B2:  19,
	ZW:  20,
	CM:  21,
	WJ:  22,
	H2:  23,
	H3:  24,
	JL:  25,
	JV:  26,
	JT:  27,
	RI:  28,
	EB:  29,
	EM:  30,
	ZWJ:  31,
	BK: 245,
	CR: 246,
	LF: 247,
	NL: 248,
	SG: 249,
	SP: 250,
	CB: 251,
	AI: 252,
	CJ: 253,
	SA: 254,
	XX: 255
};

// line break pair table in Unicode 9.0.0
// ported manually from http://unicode.org/reports/tr14/
const BREAK_PAIRS_TABLE = [
	'44444444444444444444434444444444',
	'04411444411000001100424000000001',
	'04411444411111001100424000000001',
	'44411144411111111111424111111111',
	'14411144411111111111424111111111',
	'04411144400000001100424000000001',
	'04411144400000011100424000000001',
	'04411144400101001100424000000001',
	'04411144400111001100424000000001',
	'14411144400111101100424111110111',
	'14411144400111001100424000000001',
	'14411144411111011100424000000001',
	'14411144411111011100424000000001',
	'14411144411111011100424000000001',
	'04411144401000011100424000000001',
	'04411144400000011100424000000001',
	'04410144400100001100424000000001',
	'04410144400000001100424000000001',
	'14411144411111111111424111111111',
	'04411144400000001104424000000001',
	'00000000000000000000400000000000',
	'14411144411111011100424000000001',
	'14411144411111111111424111111111',
	'04411144401000011100424000110001',
	'04411144401000011100424000010001',
	'04411144401000011100424111100001',
	'04411144401000011100424000110001',
	'04411144401000011100424000010001',
	'04411144400000001100424000001001',
	'04411144401000011100424000000011',
	'04411144401000011100424000000001',
	'04411144400000101100424000000111'
];

// line break action in Unicode 9.0.0
// ported manually from http://unicode.org/reports/tr14/
const BREAK_ACTION = {
	/*
	 * _ direct break opportunity
	 * equivalent to ÷ as defined above
	 */
	DIRECT:0,
	/*
	 * % indirect break opportunity
	 * B % A is equivalent to B × A and B SP+ ÷ A; in other words, do not break
	 * before A, unless one or more spaces follow B.
	 */
	INDIRECT:1,
	/*
	 * # indirect break opportunity for combining marks following a space
	 * B # A is equivalent to (B × A and B SP+ ÷ A), where A is of class CM.
	 */
	COMBINING_INDIRECT:2,
	/*
	 * @ prohibited break for combining marks
	 * B @ A is equivalent to B SP* × A, where A is of class CM. For more
	 * details, see Section 7.5, Combining Marks.
	 */
	COMBINING_PROHIBITED:3,
	/*
	 * ^ prohibited break
	 * B ^ A is equivalent to B SP* × A; in other words, never break before A
	 * and after B, even if one or more spaces intervene.
	 */
	PROHIBITED:4,
	/*
	 * !: B / A
	 */
	EXPLICIT:5
};

/*
 * classes
 */

function StringStream (s) {
	this.s = s || '';
	this.index = 0;
	this.goal = this.s.length;
}
StringStream.prototype = {
	get isEnd () {
		return this.index >= this.goal;
	},
	getItem: function () {
		var result = {
			codePoint:0,
			index:this.index,
			length:1
		};
		var cp = this.s.charCodeAt(this.index++), cp2;
		if (isHighSurrogate(cp)
		&& this.goal > this.index
		&& isLowSurrogate((cp2 = this.s.charCodeAt(this.index)))) {
			cp = toUCS32(cp, cp2);
			result.length++;
			this.index++;
		}
		// special wasavi behavior: control codes are stored as Unicode
		// Control Pitcures.
		else if (cp >= 0x2400 && cp <= 0x241f) {
			cp = cp & 0x00ff;
		}
		else if (cp == 0x2421) {
			cp = 0x007f;
		}
		result.codePoint = cp;
		return result;
	}
};

function LineBreakArray (s, dictData) {
	this.stream = new StringStream(s);
	this.dictData = dictData;
	this.items = [];
	this.cache = {};
}
LineBreakArray.prototype = {
	getProp: function (cp) {
		if (cp in this.cache) {
			return this.cache[cp];
		}

		const units = 7;
		var left = 0, right = ((this.dictData.length / units) >> 0) - 1;
		var middle, index, startcp, endcp;
		while (left <= right) {
			middle = ((left + right) / 2) >> 0;
			index = middle * units;
			startcp = pick3(this.dictData, index);
			endcp = pick3(this.dictData, index + 3);

			if (endcp < cp) {
				left = middle + 1;
			}
			else if (startcp > cp) {
				right = middle - 1;
			}
			else if (startcp <= cp && cp <= endcp) {
				return this.cache[cp] = this.dictData.charCodeAt(index + 6);
			}
		}
		return this.cache[cp] = BREAK_PROP.XX;
	},
	get: function (index) {
		while (this.items.length <= index && !this.stream.isEnd) {
			var item = this.stream.getItem();
			var prop = this.getProp(item.codePoint);
			// LB1 rule
			switch (prop) {
			case BREAK_PROP.AI:
			case BREAK_PROP.SG:
			case BREAK_PROP.XX:
				prop = BREAK_PROP.AL;
				break;
			case BREAK_PROP.SA:
				// TODO: distinguish general category: Mn/Mc
				prop = BREAK_PROP.AL;
				break;
			case BREAK_PROP.CJ:
				prop = BREAK_PROP.NS;
				break;
			case BREAK_PROP.CB:
				// experimental
				prop = BREAK_PROP.ID;
				break;
			}
			item.breakProp = prop;
			this.items.push(item);
		}
		return this.items[index] || false;
	}
};

function LineBreaker (dictData) {
	function findComplexBreak (props, prop, index, count) {
		if (count == 0) return 0;
		for (var i = 1; i < count; i++) {
			props.get(index + i - 1).breakAction = BREAK_ACTION.PROHIBITED;
			if (props.get(index + i).breakProp != BREAK_PROP.SA) {
				break;
			}
		}
		return i;
	}
	function run (s, callback) {
		var props = new LineBreakArray(s, dictData);
		if (props.get(0) === false) return props.items;
		typeof callback != 'function' && (callback = function () {});

		// class of 'before' character
		var prop = props.get(0).breakProp;

		// treat SP at start of input as if it followed a WJ
		if (prop == BREAK_PROP.SP) {
			prop = BREAK_PROP.WJ;
		}
		if (prop == BREAK_PROP.LF) {
			prop = BREAK_PROP.BK;
		}
		if (prop == BREAK_PROP.NL) {
			prop = BREAK_PROP.BK;
		}

		// loop over all pairs in the string up to a hard break
		for (var i = 1;
		props.get(i) !== false
		&& prop != BREAK_PROP.BK
		&& (prop != BREAK_PROP.CR || props.get(i).breakProp == BREAK_PROP.LF);
		i++) {
			var curProp = props.get(i).breakProp;

			// handle BK, NL and LF explicitly
			if (curProp == BREAK_PROP.BK
			||  curProp == BREAK_PROP.NL
			||  curProp == BREAK_PROP.LF) {
				props.get(i - 1).breakAction = BREAK_ACTION.PROHIBITED;
				prop = BREAK_PROP.BK;
				if (callback(props.get(i - 1)) === true) break;
				continue;
			}

			// handle CR explicitly
			if (curProp == BREAK_PROP.CR) {
				props.get(i - 1).breakAction = BREAK_ACTION.PROHIBITED;
				prop = BREAK_PROP.CR;
				if (callback(props.get(i - 1)) === true) break;
				continue;
			}

			// handle spaces explicitly
			if (curProp == BREAK_PROP.SP) {
				// apply rule LB7: x SP
				props.get(i - 1).breakAction = BREAK_ACTION.PROHIBITED;

				if (callback(props.get(i - 1)) === true) break;

				// do not update prop
				continue;
			}

			// handle complex scripts in a separate function
			if (curProp == BREAK_PROP.SA) {
				i += findComplexBreak(
					props, prop, i - 1, props.length - (i - 1));

				if (callback(props.get(i - 1)) === true) break;

				if (props.get(i) !== false) {
					prop = props.get(i).breakProp;
					continue;
				}
			}

			// look up pair table information in BREAK_PAIRS_TABLE [before, after];
			var breakAction;
			if (prop in BREAK_PAIRS_TABLE && curProp in BREAK_PAIRS_TABLE) {
				breakAction = BREAK_PAIRS_TABLE[prop].charAt(curProp) - 0;
			}
			else {
				breakAction = BREAK_ACTION.DIRECT;
			}

			// save break action in output array
			props.get(i - 1).breakAction = breakAction;

			// resolve indirect break
			if (breakAction == BREAK_ACTION.INDIRECT) {
				if (props.get(i - 1).breakProp == BREAK_PROP.SP) {
					props.get(i - 1).breakAction = BREAK_ACTION.INDIRECT;
				}
				else {
					props.get(i - 1).breakAction = BREAK_ACTION.PROHIBITED;
				}
			}

			// resolve combining mark break
			else if (breakAction == BREAK_ACTION.COMBINING_INDIRECT) {
				// do not break before CM
				props.get(i - 1).breakAction = BREAK_ACTION.PROHIBITED;
				if (props.get(i - 1).breakProp == BREAK_PROP.SP) {
					// new: space is not a base
					props.get(i - 1).breakAction = BREAK_ACTION.COMBINING_INDIRECT;
					/*
					// legacy: keep SP CM together
					props.get(i - 1).breakAction = BREAK_ACTION.PROHIBITED;
					if (i > 1) {
						props.get(i - 2).breakAction =
							props.get(i - 2).breakProp == BREAK_PROP.SP ?
								BREAK_ACTION.INDIRECT : BREAK_ACTION.DIRECT;
					}
					*/
					if (callback(props.get(i - 1)) === true) break;
				}
				else {
					if (callback(props.get(i - 1)) === true) break;
					continue;
				}
			}

			// this is the case OP SP* CM
			else if (breakAction == BREAK_ACTION.COMBINING_PROHIBITED) {
				// no break allowed
				props.get(i - 1).breakAction = BREAK_ACTION.COMBINING_PROHIBITED;
				if (props.get(i - 1).breakProp != BREAK_PROP.SP) {
					if (callback(props.get(i - 1)) === true) break;

					// apply rule LB9: X CM* -> X
					continue;
				}
			}

			// save prop of 'before' character (unless bypassed by 'continue')
			prop = curProp;
			if (callback(props.get(i - 1)) === true) break;
		}

		// always break at the end
		props.get(i - 1).breakAction = BREAK_ACTION.EXPLICIT;

		// purge invalid item
		while (!('breakAction' in props.items.lastItem)) {
			props.items.pop();
		}

		// return result
		return props.items;
		/*
		var last = props.items.lastItem;
		if (last.index + last.length >= s.length) {
			return props.items;
		}
		else {
			return props.items.concat(run(
				s.substring(last.index + last.length),
				callback
			));
		}
		*/
	}
	function dump (s, props) {
		var result = [];
		var fragment = '';
		for (var i = 0, goal = props.length; i < goal; i++) {
			fragment += s.substr(props[i].index, props[i].length);

			switch (props[i].breakAction) {
			case BREAK_ACTION.DIRECT:
			case BREAK_ACTION.INDIRECT:
			case BREAK_ACTION.COMBINING_INDIRECT:
			case BREAK_ACTION.EXPLICIT:
				result.push(
					'"' + toVisibleString(fragment) + '"' +
					' (' + props[i].breakAction + ')');
				fragment = '';
				break;
			}
		}
		return result.join('\n');
	}

	publish(this, run, dump);
}

function FfttDictionary (dictData) {
	var data = {}, cache = {};
	var handlers = {
		general: function (cp, data) {
			var index = find(cp, data, 3);
			if (index === false) return false;
			var result = {};
			result[data.charAt(index + 2)] = true;
			return result;
		},
		han_ja: (function () {
			// packmap info derived from Unicode 9.0.0
			// generated by "src/unicode-tools/make-fftt-hanja-dict.js --packmap"
			const packmap = {
				 0x000001: 'a'
				,0x000002: 'b'
				,0x000004: 'c'
				,0x000008: 'd'
				,0x000010: 'e'
				,0x000020: 'f'
				,0x000040: 'g'
				,0x000080: 'h'
				,0x000100: 'i'
				,0x000200: 'j'
				,0x000400: 'k'
				//omitted: 'l'
				,0x000800: 'm'
				,0x001000: 'n'
				,0x002000: 'o'
				,0x004000: 'p'
				//omitted: 'q'
				,0x008000: 'r'
				,0x010000: 's'
				,0x020000: 't'
				,0x040000: 'u'
				//omitted: 'v'
				,0x080000: 'w'
				//omitted: 'x'
				,0x100000: 'y'
				,0x200000: 'z'
			};
			return function (cp, data) {
				var index = find(cp, data, 5);
				if (index === false) return false;
				var result = {}, bits = pick3(data, index + 2);
				for (var i in packmap) {
					if (bits & (i - 0)) {
						result[packmap[i]] = true;
					}
				}
				return result;
			};
		})()
	};

	// private
	function nop () {}
	function find (cp, data, units) {
		var left = 0, right = ((data.length / units) >> 0) - 1;
		var middle, index, target;
		while (left <= right) {
			middle = ((left + right) / 2) >> 0;
			index = middle * units;
			target = pick2(data, index);

			if (target < cp) {
				left = middle + 1;
			}
			else if (target > cp) {
				right = middle - 1;
			}
			else {
				return index;
			}
		}
		return false;
	}
	function init () {
		if (!dictData) return;
		for (var i in dictData) {
			var m = 'add' + i + 'Data';
			m in this && this[m](dictData[i]);
		}
	}

	// public
	function addGeneralData (/*binary string*/d) {
		if (typeof d == 'string') {
			data.general = d;
		}
	}
	function addHanJaData (/*binary string*/d) {
		if (typeof d == 'string') {
			data.han_ja = d;
		}
	}
	function addData (/*string*/name, /*any*/d, /*function*/handler) {
		name = '' + name;
		data[name] = d;
		handlers[name] = typeof handler == 'function' ? handler : nop;
	}
	function get (/*string*/ch) {
		var result = false;
		if (ch.charCodeAt(0) <= 0x7f) {
			return result;
		}
		if (ch in cache) {
			return cache[ch];
		}
		for (var j in data) {
			var o = handlers[j](ch.charCodeAt(0), data[j]);
			if (!o) continue;
			if (result) {
				for (var k in o) {
					result[k] = o[k];
				}
			}
			else {
				result = o;
			}
		}
		return cache[ch] = result;
	}
	function match (/*string*/ch, /*string*/target) {
		if (ch == target) return true;
		var o = this.get(ch);
		return o && target in o;
	}

	//
	publish(this,
		addGeneralData, addHanJaData, addData,
		get, match
	);
	init.call(this);
}

/*
 * variables
 */

var generalSpaceRegexCache = {};

/*
 * functions
 */

function pick2 (data, index) {
	return data.charCodeAt(index)
		|  data.charCodeAt(index + 1) << 8;
}
function pick3 (data, index) {
	return data.charCodeAt(index)
		|  data.charCodeAt(index + 1) << 8
		|  data.charCodeAt(index + 2) << 16;
}
function pick4 (data, index) {
	return data.charCodeAt(index)
		|  data.charCodeAt(index + 1) << 8
		|  data.charCodeAt(index + 2) << 16
		|  data.charCodeAt(index + 3) << 24;
}
function getScriptClass (cp) {
	//                    0: space
	// (script-id << 8) | 1: letter (word component)
	// (script-id << 8) | 2: other
	var ch = String.fromCharCode(cp);
	return isSpace(ch) ?
		0 :
		(Unistring.getScriptProp(cp) << 8) | (isNonLetter(ch) ? 2 : 1);
}
function isSpace (ch) {
	return REGEX_ZS.test(ch.charAt(0));
}
function isClosedPunct (ch) {
	return REGEX_PE.test(ch.charAt(0));
}
function isSTerm (ch) {
	return REGEX_STERM.test(ch.charAt(0));
}
function isPTerm (ch) {
	return REGEX_PTERM.test(ch.charAt(0));
}
function isIdeograph (ch) {
	return REGEX_HAN_FAMILY.test(ch.charAt(0));
}
function isNonLetter (ch) {
	return REGEX_NON_LETTER.test(ch.charAt(0));
}
function isHighSurrogate (cp) {
	return cp >= 0xd800 && cp <= 0xdb7f;
}
function isLowSurrogate (cp) {
	return cp >= 0xdc00 && cp <= 0xdfff;
}
function toUCS32 (hcp, lcp) {
	return ((hcp & 0x03c0) + 0x0040) << 10
		| (hcp & 0x003f) << 10
		| (lcp & 0x03ff);
}
function toUTF16 (cp) {
	var p = (cp & 0x1f0000) >> 16;
	var o = cp & 0xffff;
	return p ?
		String.fromCharCode(0xd800 | ((p - 1) << 6) | ((o & 0xfc00) >> 10)) + String.fromCharCode(0xdc00 | (o & 0x03ff)) :
		String.fromCharCode(o);
}
function canBreak (act) {
	return act == BREAK_ACTION.DIRECT
		|| act == BREAK_ACTION.INDIRECT
		|| act == BREAK_ACTION.COMBINING_INDIRECT
		|| act == BREAK_ACTION.EXPLICIT;
}

function getUnicodeGeneralSpaceRegex (source, opts) {
	var g = /g/.test(opts);
	if (source in generalSpaceRegexCache && !g) {
		return generalSpaceRegexCache[source];
	}
	var s = source;
	s = s.replace(/S/, REGEX_ZS.source);
	s = s.replace(/(\[[^\[\]]*)\[/g, '$1');
	s = s.replace(/\]([^\[\]]*\])/g, '$1');
	if (g) {
		return new RegExp(s, opts);
	}
	else {
		return generalSpaceRegexCache[source] = new RegExp(s, opts);
	}
}

var unicodeUtils = Object.freeze({
	BREAK_PROP:BREAK_PROP,
	BREAK_ACTION:BREAK_ACTION,

	LineBreaker:LineBreaker,
	FfttDictionary:FfttDictionary,

	getScriptClass:getScriptClass,
	isSpace:isSpace,
	isClosedPunct:isClosedPunct,
	isSTerm:isSTerm,
	isPTerm:isPTerm,
	isIdeograph:isIdeograph,
	isNonLetter:isNonLetter,
	isHighSurrogate:isHighSurrogate,
	isLowSurrogate:isLowSurrogate,
	toUCS32:toUCS32,
	toUTF16:toUTF16,
	canBreak:canBreak,
	getUnicodeGeneralSpaceRegex:getUnicodeGeneralSpaceRegex
});

if (typeof module !== 'undefined' && typeof exports !== 'undefined') {
	exports.unicodeUtils = unicodeUtils;
	exports.spc = unicodeUtils.getUnicodeGeneralSpaceRegex;
}
else {
	g.unicodeUtils = unicodeUtils;
	g.spc = unicodeUtils.getUnicodeGeneralSpaceRegex;
}

})(typeof global == 'object' ? global : window);

// vim:set ts=4 sw=4 fenc=UTF-8 ff=unix ft=javascript fdm=marker :
